package course.p3_arraysSort.exa02_insertSort;

import java.util.Arrays;

/**
 * 插入排序
 */
public class InsertSort {

    /**
     * 插入排序核心实现
     * @param array 排序数组
     */
    public static <T extends Comparable<T>> T[] sort(T[] array) {
        for(int i=1;i < array.length;i++){
            int j = i-1;
            if(array[j].compareTo(array[i])>0) {
                T temp = array[j];
                array[j] = array[i];
                array[i] = temp;
                while(j>0&&array[j-1].compareTo(array[j])>0) {
                    T tem = array[j];
                    array[j] = array[j-1];
                    array[j-1] = tem;
                    j--;
                }
            }
        }
        return array;
    }

    /**
     * 插入排序方法实现
     * @param array
     */
    public static void insertSort(int[] array) {
        int temp;
        int j;
        for(int i=1;i<array.length;i++){
            temp = array[i];
            for(j=i;j>0&&array[j-1]>temp;j--){
                array[j] = array[j-1];
            }
            array[j] = temp;
        }
    }


    public static void insertSortTest() {
        Integer[] numbs = {3,9,2,5,7};
        sort(numbs);
        System.out.println(Arrays.toString(numbs));
        int[] numbs1 = {3,9,2,5,7};
        insertSort(numbs1);
        System.out.println(Arrays.toString(numbs1));
    }


    public static void main(String[] args) {
        insertSortTest();
    }



}
